<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.1.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/oldimgs/32.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/oldimgs/16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=sans-serif:300,300italic,400,400italic,700,700italic|Ubuntu:300,300italic,400,400italic,700,700italic|Roboto:300,300italic,400,400italic,700,700italic|'Open+Sans':300,300italic,400,400italic,700,700italic|'Microsoft+YaHei':300,300italic,400,400italic,700,700italic|sans-serif;:300,300italic,400,400italic,700,700italic|Source+Code+Pro:300,300italic,400,400italic,700,700italic|monospace:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">

<link rel="stylesheet" href="//cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.14.0/css/all.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/pace-js@1.0.2/themes/blue/pace-theme-minimal.css">
  <script src="//cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

<script class="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"http:/ShuYuMo2003.github.io","root":"/","scheme":"Mist","version":"8.0.0","exturl":false,"sidebar":{"position":"left","width":230,"display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
  </script>

  <meta name="description" content="ProblemsA将 $n$ 个石子分成 $x$ 堆，使每一堆的石子个数都形如 $ 3k^2 - 3k + 1$ $(k \le 1)$。最小化 $x$ 输出 $x$。 $n \le 10^{11}$   B给出一个字符串 $S$ ，求出字符串中，有多少连续的子串形如 $A A_r A$ 。  其中 $A_r$ 表示 $A$ 的反串。合法的相同字串出现多次，统计多次。 $|S| \le 2 \ti">
<meta property="og:type" content="article">
<meta property="og:title" content="【ZROI 2020 提高 十连测】Day1">
<meta property="og:url" content="2020/%E3%80%90ZROI-2020-%E5%8D%81%E8%BF%9E%E6%B5%8B%E3%80%91Day1/index.html">
<meta property="og:site_name" content="Shu Yu Mo&#39;s blog">
<meta property="og:description" content="ProblemsA将 $n$ 个石子分成 $x$ 堆，使每一堆的石子个数都形如 $ 3k^2 - 3k + 1$ $(k \le 1)$。最小化 $x$ 输出 $x$。 $n \le 10^{11}$   B给出一个字符串 $S$ ，求出字符串中，有多少连续的子串形如 $A A_r A$ 。  其中 $A_r$ 表示 $A$ 的反串。合法的相同字串出现多次，统计多次。 $|S| \le 2 \ti">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-08-31T00:21:06.000Z">
<meta property="article:modified_time" content="2020-09-01T01:10:06.484Z">
<meta property="article:author" content="舒雨墨">
<meta property="article:tag" content="Shu Yu Mo&#39;s blog">
<meta property="article:tag" content="Blog">
<meta property="article:tag" content="OI">
<meta property="article:tag" content="Dr_OldSu">
<meta property="article:tag" content="舒阳">
<meta property="article:tag" content="life">
<meta property="article:tag" content="生活">
<meta property="article:tag" content="信息竞赛">
<meta property="article:tag" content="Shu_Yu_Mo">
<meta property="article:tag" content="ShuYuMo">
<meta property="article:tag" content="东营市第一中学">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="2020/【ZROI-2020-十连测】Day1/">


<script data-pjax class="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>【ZROI 2020 提高 十连测】Day1 | Shu Yu Mo's blog</title>
  






  <noscript>
  <style>
  body { margin-top: 2rem; }

  .use-motion .menu-item,
  .use-motion .sidebar,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header {
    visibility: visible;
  }

  .use-motion .header,
  .use-motion .site-brand-container .toggle,
  .use-motion .footer { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle,
  .use-motion .custom-logo-image {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line {
    transform: scaleX(1);
  }

  .search-pop-overlay, .sidebar-nav { display: none; }
  .sidebar-panel { display: block; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">Shu Yu Mo's blog</h1>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">远行者</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-links">

    <a href="/link/" rel="section"><i class="fa fa-th fa-fw"></i>links</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
        <li class="menu-item menu-item-templates">

    <a href="/port/" rel="section"><i class="fa fa-heartbeat fa-fw"></i>Templates</a>

  </li>
        <li class="menu-item menu-item-latex">

    <a href="/LaTeX-syntax.html" rel="section"><i class="fa fa-heartbeat fa-fw"></i>LaTeX</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-sitemap fa-fw"></i>站点地图</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav" style="display:none;">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <section class="post-toc-wrap sidebar-panel">

        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



        <hr/>
          <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#Problems"><span class="nav-number">1.</span> <span class="nav-text">Problems</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#A"><span class="nav-number">1.0.1.</span> <span class="nav-text">A</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#B"><span class="nav-number">1.0.2.</span> <span class="nav-text">B</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#C"><span class="nav-number">1.0.3.</span> <span class="nav-text">C</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Problem-A-Stone"><span class="nav-number">2.</span> <span class="nav-text">Problem A Stone</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Statement"><span class="nav-number">2.1.</span> <span class="nav-text">Statement</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Analysis"><span class="nav-number">2.2.</span> <span class="nav-text">Analysis</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%BC%95%E7%90%86-1"><span class="nav-number">2.2.1.</span> <span class="nav-text">引理 1</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%BC%95%E7%90%86-2"><span class="nav-number">2.2.2.</span> <span class="nav-text">引理 2</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E8%AF%81%E6%98%8E-%E5%BC%95%E7%90%86-2"><span class="nav-number">2.2.3.</span> <span class="nav-text">证明 引理 2</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%BC%95%E7%90%86-3"><span class="nav-number">2.2.4.</span> <span class="nav-text">引理 3</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#%E8%AF%81%E6%98%8E-%E5%BC%95%E7%90%86-3"><span class="nav-number">2.2.5.</span> <span class="nav-text">证明 引理 3</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Problem-B-Palindrome"><span class="nav-number">3.</span> <span class="nav-text">Problem B Palindrome</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Statement-1"><span class="nav-number">3.1.</span> <span class="nav-text">Statement</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Analysis-1"><span class="nav-number">3.2.</span> <span class="nav-text">Analysis</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Problem-C-Random"><span class="nav-number">4.</span> <span class="nav-text">Problem C Random</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#%E5%85%B3%E4%BA%8E%E6%9C%9F%E6%9C%9B%E6%80%9D%E8%80%83"><span class="nav-number">4.0.1.</span> <span class="nav-text">关于期望思考</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Codes"><span class="nav-number">5.</span> <span class="nav-text">Codes</span></a></li></ol></div>
      </section>
      <!--/noindex-->

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="舒雨墨"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">舒雨墨</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">106</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
        <span class="site-state-item-count">28</span>
        <span class="site-state-item-name">分类</span>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author animated">
      <span class="links-of-author-item">
        <a href="https://github.com/ShuYuMo2003" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;ShuYuMo2003" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.luogu.com.cn/user/44615" title="Luogu → https:&#x2F;&#x2F;www.luogu.com.cn&#x2F;user&#x2F;44615" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>Luogu</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:sujiayi2003@gmail.com" title="E-Mail → mailto:sujiayi2003@gmail.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://twitter.com/JiaYiSu5" title="Twitter → https:&#x2F;&#x2F;twitter.com&#x2F;JiaYiSu5" rel="noopener" target="_blank"><i class="fab fa-twitter fa-fw"></i>Twitter</a>
      </span>
  </div>



      </section>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">
      

      

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="/2020/【ZROI-2020-十连测】Day1/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="舒雨墨">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Shu Yu Mo's blog">
    </span>

    
    
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          【ZROI 2020 提高 十连测】Day1
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-08-31 08:21:06" itemprop="dateCreated datePublished" datetime="2020-08-31T08:21:06+08:00">2020-08-31</time>
    </span>
      <span class="post-meta-item">
        <span class="post-meta-item-icon">
          <i class="far fa-calendar-check"></i>
        </span>
        <span class="post-meta-item-text">更新于</span>
        <time title="修改时间：2020-09-01 09:10:06" itemprop="dateModified" datetime="2020-09-01T09:10:06+08:00">2020-09-01</time>
      </span>

  
    <span id="2020/【ZROI-2020-十连测】Day1/" class="post-meta-item leancloud_visitors" data-flag-title="【ZROI 2020 提高 十连测】Day1" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="far fa-comment"></i>
      </span>
      <span class="post-meta-item-text">Valine：</span>
    
    <a title="valine" href="/2020/【ZROI-2020-十连测】Day1/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="2020/【ZROI-2020-十连测】Day1/" itemprop="commentCount"></span>
    </a>
  </span>
  
  
      </div>
      <div class="post-meta">
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>6.7k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>6 分钟</span>
    </span>
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="Problems"><a href="#Problems" class="headerlink" title="Problems"></a>Problems</h2><div class="note success"><h4 id="A"><a href="#A" class="headerlink" title="A"></a>A</h4><p>将 $n$ 个石子分成 $x$ 堆，使每一堆的石子个数都形如 $ 3k^2 - 3k + 1$ $(k \le 1)$。最小化 $x$ 输出 $x$。</p>
<p>$n \le 10^{11}$</p>
</div>

<div class="note success"><h4 id="B"><a href="#B" class="headerlink" title="B"></a>B</h4><p>给出一个字符串 $S$ ，求出字符串中，有多少连续的子串形如 $A A_r A$ 。 </p>
<p>其中 $A_r$ 表示 $A$ 的反串。合法的相同字串出现多次，统计多次。</p>
<p>$|S| \le 2 \times 10^6$</p>
</div>

<div class="note success"><h4 id="C"><a href="#C" class="headerlink" title="C"></a>C</h4><p>给出一个 $n$ 个点的树（保证这棵树<strong>随机生成</strong>），点有点权， 规定 $1$ 号点为根节点。 </p>
<p><strong>随机</strong>生成一个 $n$ 排列，按这个排列的顺序依次访问所有树上的节点。每次访问到一个结点 $x$ 时，需要将包括 $x$ 在内的所有 $x$ 子树中的点的点权 $V$ 加上 $x$ 点的当前权值 $V^{‘}_x$。</p>
<p>求出最终所有点权和的期望值。</p>
<p>$n \le 10^5$</p>
</div>

<hr>
<a id="more"></a>

<h2 id="Problem-A-Stone"><a href="#Problem-A-Stone" class="headerlink" title="Problem A Stone"></a>Problem A Stone</h2><h3 id="Statement"><a href="#Statement" class="headerlink" title="Statement"></a>Statement</h3><div class="note info"><p>将 $n$ 个石子分成 $x$ 堆，使每一堆的石子个数都形如 $ 3k^2 - 3k + 1$ $(k \le 1)$。最小化 $x$ 输出 $x$。</p>
<p>$n \le 10^11$</p>
</div>

<h3 id="Analysis"><a href="#Analysis" class="headerlink" title="Analysis"></a>Analysis</h3><div class="note primary"><h4 id="引理-1"><a href="#引理-1" class="headerlink" title="引理 1"></a>引理 1</h4><p>对于任意一个正整数 $x$， 均可以被拆分为 $3$ 个形如 $\dbinom{n}{2}$ 的数字。</p>
</div>
<div class="note primary"><h4 id="引理-2"><a href="#引理-2" class="headerlink" title="引理 2"></a>引理 2</h4><p>可以证明 $x$ 一定小于等于 $8$。</p>
</div>

<h4 id="证明-引理-2"><a href="#证明-引理-2" class="headerlink" title="证明 引理 2"></a>证明 引理 2</h4><p>我们需要的数字是 $3k^2 - 3k + 1 = 6 \times \dfrac{n (n + 1)}{2} + 1 = 6 \times \dbinom{n}{2} + 1$.</p>
<p>考虑一定存在 $N - k$ 是 $6$ 的倍数。 所以 $N - k + 3$ 必然可以写成 三个形如 $3k^2 - 3k + 1$ 数的和的形式.</p>
<p>而 $N - k + 3$ 最多和 $N$ 相差 $5$ 所以最多补 $5$ 个 $1$ 就可以凑出 $N$.</p>
<div class="note primary"><h4 id="引理-3"><a href="#引理-3" class="headerlink" title="引理 3"></a>引理 3</h4><p>$ans \equiv N\ \ (mod\ \ 6)$</p>
</div>
<h4 id="证明-引理-3"><a href="#证明-引理-3" class="headerlink" title="证明 引理 3"></a>证明 引理 3</h4><p>因为 $\sum 3k^2 - 3k + 1 = \sum 6 \times \dfrac{n (n + 1)}{2} + 1 = \sum 6 \times \dbinom{n}{2} + 1$.</p>
<p>显然 $\sum 6 \times \dbinom{n}{2} + 1 \equiv 1\ \ (mod\ \ 6)$.</p>
<p>易知 $ans \equiv N\ \ (mod\ \ 6)$</p>
<p>只需要判断答案是 $1$ 还是 $7$， 是 $2$ 还是 $8$。</p>
<ul>
<li>判断是否为 $1$ 直接判断即可。</li>
<li>判断是否为 $2$ 双指针扫一遍即可。</li>
</ul>
<hr>
<h2 id="Problem-B-Palindrome"><a href="#Problem-B-Palindrome" class="headerlink" title="Problem B Palindrome"></a>Problem B Palindrome</h2><h3 id="Statement-1"><a href="#Statement-1" class="headerlink" title="Statement"></a>Statement</h3><div class="note info"><p>给出一个字符串，求出字符串中，有多少连续的子串形如 $A A_r A$ 。 </p>
<p>其中 $A_r$ 表示 $A$ 的反串。合法的相同字串出现多次，统计多次。</p>
<p>$|S| \le 2 \times 10^6$</p>
</div>
<h3 id="Analysis-1"><a href="#Analysis-1" class="headerlink" title="Analysis"></a>Analysis</h3><p>先用各种神奇的算法（<code>字符串 Hash</code> 、<code>manacher</code>）求出 <code>len[i]</code> 表示第 $i$ 个字符和第 $i + 1$ 个字符之间为中心，向两边扩展最长的回文串.</p>
<p>枚举 $A A_r A$ 的 $\frac{1}{3}$ 位置 $i$ ，在 $[i + 1, i + \text{len}[i]]$ 这个区间中有多少 $x$ 满足 $x - \text{len}[x] \le i$， 每一个合法的 $x$ 给答案贡献 $1$.</p>
<p>转化为<mark class="label info">二维数点</mark>问题.</p>
<mark class="label info">静态二维数点</mark>可以采用 <mark class="label primary">主席树</mark> 或者<mark class="label danger">离线</mark>后采用 <mark class="label primary">树状数组</mark> 扫描.

<hr>
<h2 id="Problem-C-Random"><a href="#Problem-C-Random" class="headerlink" title="Problem C Random"></a>Problem C Random</h2><div class="note info"><p>给出一个 $n$ 个点的树（保证这棵树<strong>随机生成</strong>），点有点权， 规定 $1$ 号点为根节点。 </p>
<p><strong>随机</strong>生成一个 $n$ 排列，按这个排列的顺序依次访问所有树上的节点。每次访问到一个结点 $x$ 时，需要将包括 $x$ 在内的所有 $x$ 子树中的点，点权加 $V_x$。</p>
<p>$n \le 10^5$</p>
</div>


<div class="note danger"><h4 id="关于期望思考"><a href="#关于期望思考" class="headerlink" title="关于期望思考"></a>关于期望思考</h4><p>期望的<mark class="label primary">线性性</mark>：标志着很多情况下的期望可以分开算，算完后再合并。例如：点权和的期望 $=$ 点权的期望和。</p>
<p>直观感受一下：期望是一个随机变量的平均情况下的数值。</p>
<p>我们不知道这个随机变量$x$确切的数值，自然也不知道由这个随机变量推导出来的另一个随机变量$X$（例如：如果我们不知道 每个点 操作后的 <strong>确切点权</strong>，那么所有点的点权和的<strong>确切数值</strong>也无从得知。）</p>
<p>但是如果我们知道每个点在<mark class="label info">平均意义</mark>下取到的值$x$，我们一样可以通过随机变量$x$<mark class="label info">平均意义</mark>下取到的值推出$X$在<mark class="label info">平均意义</mark>下取到的值。</p>
</div>

<p>关于本题，我们同样可以拆开来看，要求 求出结点的期望和，那我们可以求出每个点的期望权值，然后再相加就能得到所有结点的期望和。</p>
<p>对于一个有根树上的每一个结点，可能能对这个结点的权值产生贡献的<mark class="label danger">是且仅是</mark>它的祖先。</p>
<p>这个点 $a$ 最终权值的期望 $V^{‘}_a$ 就是点 $a$ 的初始权值和所有 $a$ 的祖先对点 $a$ 的期望贡献之和。</p>
<p> $a$ 的祖先 $p$ 对 $a$ 的期望贡献可以拆成 $V^{‘}_p$ 与 对 $a$ 的贡献次数的乘积。</p>
<p>对于每一条树链上的任意一个点 $x$ 来说某一个祖先 $p$ 对其贡献的次数，只与这个祖先$p$和这个点$x$的距离有关。</p>
<p>不妨定义 $\text{dp}[i]$ 为结点 $1$ 到往下的第 $i$ 个点的期望贡献次数（<mark class="label danger">note</mark>：第 $1$ 个点对第 $1$ 个点的贡献次数定义为 $\text{dp}[1]$ ）。</p>
<p>对于每一条树链，我们都可以采用同一套 $\text{dp}$ 值进行处理，因为对于每个点来说，其祖先的对其贡献次数只与他们之间的相对位置有关。</p>
<p>考虑如何预处理出 $\text{dp}[i]$：</p>
<div class="note success"><p>考虑结点 $1$ 如何对其往下第 $i - 1$ 结点 $x$ 产生贡献。（不妨设：这一条树链上结点的编号由<mark class="label danger">浅到深</mark>依次为 $1-k$ ）。</p>
<p>考虑贡献的传递过程，结点 $1$ 的贡献传给 $x$ 有两种情况：</p>
<ul>
<li><p>由 $1$ 直接传递给 $x$</p>
</li>
<li><p>由 $1$ 传递给 $x$ 的中间的若干结点，经过多次传递后传递给 $x$ 。</p>
</li>
</ul>
<p>这些方案对应的贡献为 $1$ ，所以只要求出方案数量，就可以求出结点 $1$ 对 $x$ 的贡献次数。</p>
<p>考虑这些方案对应着什么—— $n$ 的排列中 以 $1$ 开始的<strong>上升序列</strong>的个数。</p>
<p>于是，$\text{dp}[i]$ 就等于在 $n$ 的排列中 以 $1$ 开始的<strong>上升序列</strong>的个数。</p>
<p>枚举一个上升序列的长度 $d$ ，统计其数量即可</p>
<p>$$\begin{equation*} \text{dp}[i] = \sum_{d = 1}^{i} \dbinom{i - 1}{d - 1} \times \dbinom{i}{d} \times (i - d)! \end{equation*}$$</p>
<p>其中：</p>
<ul>
<li><p>$\dbinom{i - 1}{d - 1}$ 指在 $i - 1$ 中选定 $d - 1$ 个数字<mark class="label danger">(已经强制 $1$ 为开头了)</mark>。</p>
</li>
<li><p>$\dbinom{i}{d}$ 指在 $i$ 个位置中选 $d$ 个将这 $d$ 个数字放下。</p>
</li>
<li><p>$(i - d)!$ 指 剩下的$(i - d)$个位置的数字任意排列。</p>
</li>
</ul>
</div>
<div class="note danger"><p>最后需要注意一点，因为树是随机生成的，其实这就保证了树的高度（树链的最长长度）在$O(\sqrt n)$级别，预处理和统计答案相当于是线性的。</p>
</div>

<h2 id="Codes"><a href="#Codes" class="headerlink" title="Codes"></a>Codes</h2><div class="tabs" id="codes"><ul class="nav-tabs"><li class="tab active"><a href="#codes-1">Code A</a></li><li class="tab"><a href="#codes-2">Code B</a></li><li class="tab"><a href="#codes-3">Code C</a></li></ul><div class="tab-content"><div class="tab-pane active" id="codes-1"><pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">1e7</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">LL <span class="token keyword">long</span> <span class="token keyword">long</span> </span></span>
LL <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> LL x<span class="token punctuation">;</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%lld"</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> x<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
LL A<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">,</span> Q<span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token punctuation">(</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span> <span class="token number">1e11</span><span class="token punctuation">)</span> <span class="token keyword">break</span><span class="token punctuation">;</span> <span class="token keyword">else</span> Q <span class="token operator">=</span> i<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">doit</span><span class="token punctuation">(</span>LL x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">%</span> <span class="token number">6</span> <span class="token operator">!=</span> <span class="token number">1</span> <span class="token operator">&amp;&amp;</span> x <span class="token operator">%</span> <span class="token number">6</span> <span class="token operator">!=</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token keyword">return</span> x <span class="token operator">%</span> <span class="token number">6</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">?</span> <span class="token number">6</span> <span class="token operator">:</span> x <span class="token operator">%</span> <span class="token number">6</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x <span class="token operator">%</span> <span class="token number">6</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        x <span class="token operator">=</span> <span class="token punctuation">(</span>x <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">6</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token punctuation">(</span> <span class="token operator">*</span><span class="token function">lower_bound</span><span class="token punctuation">(</span>A <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> A <span class="token operator">+</span> Q <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> x<span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token punctuation">(</span> x <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token number">7</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span> <span class="token keyword">else</span> <span class="token punctuation">&#123;</span>
        x <span class="token operator">=</span> <span class="token punctuation">(</span>x <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">6</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> L <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">,</span> R <span class="token operator">=</span> Q<span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>L <span class="token operator">&lt;=</span> R<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span>L<span class="token punctuation">]</span> <span class="token operator">+</span> A<span class="token punctuation">[</span>R<span class="token punctuation">]</span> <span class="token operator">==</span> x<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">2</span><span class="token punctuation">;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span>R<span class="token punctuation">]</span> <span class="token operator">+</span> A<span class="token punctuation">[</span>L<span class="token punctuation">]</span> <span class="token operator">&lt;</span> x<span class="token punctuation">)</span> L<span class="token operator">++</span><span class="token punctuation">;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span>R<span class="token punctuation">]</span> <span class="token operator">+</span> A<span class="token punctuation">[</span>L<span class="token punctuation">]</span> <span class="token operator">></span> x<span class="token punctuation">)</span> R<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">return</span> <span class="token number">8</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> T <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>T<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> <span class="token function">doit</span><span class="token punctuation">(</span><span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre></div><div class="tab-pane" id="codes-2"><pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;ctime></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">2e7</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">LL <span class="token keyword">long</span> <span class="token keyword">long</span> </span></span>
<span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> x<span class="token punctuation">;</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> x<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">char</span> S<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span>  n<span class="token punctuation">;</span>
<span class="token keyword">namespace</span> Hash<span class="token punctuation">&#123;</span>
    <span class="token keyword">const</span> <span class="token keyword">int</span> MOD  <span class="token operator">=</span> <span class="token number">998244353</span><span class="token punctuation">;</span>
    <span class="token keyword">const</span> <span class="token keyword">int</span> base <span class="token operator">=</span> <span class="token string">'z'</span> <span class="token operator">+</span> <span class="token number">10</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> ahs<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> bhs<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> POW<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> <span class="token function">pow</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">,</span> <span class="token keyword">int</span> p<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>b <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">*</span><span class="token number">1LL</span><span class="token operator">*</span> a<span class="token punctuation">)</span> <span class="token operator">%</span> p<span class="token punctuation">;</span> a <span class="token operator">=</span> <span class="token punctuation">(</span>a <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a<span class="token punctuation">)</span> <span class="token operator">%</span> p<span class="token punctuation">;</span> b <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">return</span> ans<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">int</span> <span class="token function">suba</span><span class="token punctuation">(</span><span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>  ahs<span class="token punctuation">[</span>R<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token punctuation">(</span>ahs<span class="token punctuation">[</span>L <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> POW<span class="token punctuation">[</span>R <span class="token operator">-</span> L <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span>  <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> MOD<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">int</span> <span class="token function">subb</span><span class="token punctuation">(</span><span class="token keyword">int</span> L<span class="token punctuation">,</span> <span class="token keyword">int</span> R<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>  bhs<span class="token punctuation">[</span>L<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token punctuation">(</span>bhs<span class="token punctuation">[</span>R <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> POW<span class="token punctuation">[</span>R <span class="token operator">-</span> L <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span>  <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> MOD<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">void</span> <span class="token function">initHash</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        POW<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> x<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> POW<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> POW<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> base <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> x<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            ahs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span>ahs<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> base<span class="token punctuation">)</span> <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> S<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> x<span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            bhs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span> <span class="token punctuation">(</span>bhs<span class="token punctuation">[</span>i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> base<span class="token punctuation">)</span> <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> S<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">using</span> Hash<span class="token operator">::</span>initHash<span class="token punctuation">;</span>
<span class="token keyword">using</span> Hash<span class="token operator">::</span>suba<span class="token punctuation">;</span>
<span class="token keyword">using</span> Hash<span class="token operator">::</span>subb<span class="token punctuation">;</span>
<span class="token keyword">int</span> mlen<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> qury<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    clock_t t0 <span class="token operator">=</span> <span class="token function">clock</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">freopen</span><span class="token punctuation">(</span><span class="token string">"in.txt"</span><span class="token punctuation">,</span> <span class="token string">"r"</span><span class="token punctuation">,</span> <span class="token constant">stdin</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span> S <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> n <span class="token operator">=</span> <span class="token function">strlen</span><span class="token punctuation">(</span>S <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">initHash</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>S<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> S<span class="token punctuation">[</span>i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> mlen<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token keyword">continue</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
        <span class="token keyword">int</span> L <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> R <span class="token operator">=</span> i<span class="token punctuation">;</span>
        <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>L <span class="token operator">&lt;</span> R<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">int</span> mid <span class="token operator">=</span> L <span class="token operator">+</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>R <span class="token operator">-</span> L <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">>></span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">suba</span><span class="token punctuation">(</span>i <span class="token operator">-</span> mid <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token function">subb</span><span class="token punctuation">(</span>i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> i <span class="token operator">+</span> mid<span class="token punctuation">)</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> mid<span class="token punctuation">,</span> L <span class="token operator">=</span> mid<span class="token punctuation">;</span>
            <span class="token keyword">else</span> R <span class="token operator">=</span> mid <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
        mlen<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> ans<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> qury<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> i <span class="token operator">-</span> mlen<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>

    <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> i <span class="token operator">+</span> mlen<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span> ans <span class="token operator">+=</span> <span class="token punctuation">(</span>j <span class="token operator">-</span> mlen<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&lt;=</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span> ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre></div><div class="tab-pane" id="codes-3"><pre class="line-numbers language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;stack></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token expression">MOD <span class="token number">1000000007</span></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> x<span class="token punctuation">;</span> <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span> <span class="token operator">&amp;</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> x<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> _ <span class="token operator">=</span> <span class="token number">1e5</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> MAXD <span class="token operator">=</span> <span class="token number">1e3</span> <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> head<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">edges</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> node<span class="token punctuation">;</span>
    <span class="token keyword">int</span> nxt<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>edge<span class="token punctuation">[</span>_ <span class="token operator">&lt;&lt;</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> tot <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">,</span> <span class="token keyword">int</span> v<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    tot<span class="token operator">++</span><span class="token punctuation">;</span>
    edge<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>node <span class="token operator">=</span> v<span class="token punctuation">;</span>
    edge<span class="token punctuation">[</span>tot<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt  <span class="token operator">=</span> head<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">;</span>
    head<span class="token punctuation">[</span>u<span class="token punctuation">]</span>        <span class="token operator">=</span> tot<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> n<span class="token punctuation">;</span>
<span class="token keyword">int</span> rt <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> C<span class="token punctuation">[</span>MAXD <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">[</span>MAXD <span class="token operator">+</span> <span class="token number">100</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> frc<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> dp<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> <span class="token function">pow</span><span class="token punctuation">(</span><span class="token keyword">int</span> a<span class="token punctuation">,</span> <span class="token keyword">int</span> b<span class="token punctuation">,</span> <span class="token keyword">int</span> P<span class="token punctuation">)</span>  <span class="token punctuation">&#123;</span> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span> <span class="token keyword">if</span><span class="token punctuation">(</span>b <span class="token operator">&amp;</span> <span class="token number">1</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a<span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span> a <span class="token operator">=</span> <span class="token punctuation">(</span>a <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> a<span class="token punctuation">)</span> <span class="token operator">%</span> P<span class="token punctuation">;</span> b <span class="token operator">>>=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">return</span> ans<span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">inv</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token function">pow</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> MOD <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">,</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
<span class="token keyword">const</span> <span class="token keyword">int</span> DB <span class="token operator">=</span> <span class="token number">20</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    C<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> MAXD<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        C<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;=</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            C<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span> C<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> C<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    frc<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> _ <span class="token operator">-</span> <span class="token number">10</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> frc<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span> frc<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> MAXD<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> d <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> d <span class="token operator">&lt;=</span> i<span class="token punctuation">;</span> d<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token punctuation">(</span>
                <span class="token punctuation">(</span>  <span class="token punctuation">(</span> <span class="token punctuation">(</span>C<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>d <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> C<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>d<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD <span class="token punctuation">)</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> frc<span class="token punctuation">[</span>i <span class="token operator">-</span> d<span class="token punctuation">]</span>  <span class="token punctuation">)</span> <span class="token operator">%</span> MOD
                    <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> MAXD<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> <span class="token function">inv</span><span class="token punctuation">(</span>frc<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token keyword">struct</span> <span class="token class-name">Stack</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> v<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token keyword">int</span> top<span class="token punctuation">;</span> <span class="token function">Stack</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> top <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">inline</span> <span class="token keyword">int</span> <span class="token operator">*</span><span class="token function">GetHead</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token operator">&amp;</span>v<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">inline</span> <span class="token keyword">int</span><span class="token operator">*</span> <span class="token function">GetTail</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">return</span> <span class="token operator">&amp;</span>v<span class="token punctuation">[</span>top<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>v<span class="token punctuation">[</span>top<span class="token operator">++</span><span class="token punctuation">]</span> <span class="token operator">=</span> x<span class="token punctuation">;</span><span class="token punctuation">&#125;</span> <span class="token keyword">void</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>top <span class="token operator">--</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span> <span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
Stack S<span class="token punctuation">;</span>
<span class="token keyword">int</span> val<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> NodeVal<span class="token punctuation">[</span>_<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">void</span> <span class="token function">dfs0</span><span class="token punctuation">(</span><span class="token keyword">int</span> o<span class="token punctuation">,</span> <span class="token keyword">int</span> fa<span class="token punctuation">,</span> <span class="token keyword">int</span> dep<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    S<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>o<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> now <span class="token operator">=</span> dep<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> <span class="token operator">*</span>i <span class="token operator">=</span> S<span class="token punctuation">.</span><span class="token function">GetHead</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i <span class="token operator">!=</span> S<span class="token punctuation">.</span><span class="token function">GetTail</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        val<span class="token punctuation">[</span>o<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>  val<span class="token punctuation">[</span>o<span class="token punctuation">]</span> <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> <span class="token punctuation">(</span>dp<span class="token punctuation">[</span>now<span class="token punctuation">]</span> <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> NodeVal<span class="token punctuation">[</span><span class="token operator">*</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD  <span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
        now <span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> head<span class="token punctuation">[</span>o<span class="token punctuation">]</span><span class="token punctuation">;</span> i <span class="token punctuation">;</span> i <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>nxt<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> ex <span class="token operator">=</span> edge<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">.</span>node<span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ex <span class="token operator">==</span> fa<span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
        <span class="token function">dfs0</span><span class="token punctuation">(</span>ex<span class="token punctuation">,</span> o<span class="token punctuation">,</span> dep <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    S<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    n <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span> <span class="token keyword">int</span> u <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> v <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span>u<span class="token punctuation">,</span> v<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token function">add</span><span class="token punctuation">(</span>v<span class="token punctuation">,</span> u<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> NodeVal<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">read</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">dfs0</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> NodeVal<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> ans <span class="token operator">=</span> <span class="token punctuation">(</span>ans <span class="token operator">+</span><span class="token number">0ll</span><span class="token operator">+</span> val<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d\n"</span><span class="token punctuation">,</span> <span class="token punctuation">(</span>ans <span class="token operator">*</span><span class="token number">1ll</span><span class="token operator">*</span> frc<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre></div></div></div>
    </div>

    
    
    

    <footer class="post-footer">

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2020/【ZROI-1198】异或/" rel="prev" title="【ZROI-1198】异或">
                  <i class="fa fa-chevron-left"></i> 【ZROI-1198】异或
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2020/「学习总结」久月-第一周/" rel="next" title="「学习总结」久月 第一周">
                  「学习总结」久月 第一周 <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
  
  
  



      
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      const activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      const commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

    </div>
  </main>

  <footer class="footer">
    <div class="footer-inner">
      

      

<div class="copyright">
  
  &copy; 2018 – 
  <span itemprop="copyrightYear">2021</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">舒雨墨</span>
</div>
<div class="wordcount">
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-chart-line"></i>
    </span>
    <span title="站点总字数">319k</span>
  </span>
  <span class="post-meta-item">
    <span class="post-meta-item-icon">
      <i class="fa fa-coffee"></i>
    </span>
    <span title="站点阅读时长">4:50</span>
  </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/mist/" class="theme-link" rel="noopener" target="_blank">NexT.Mist</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <script src="//cdn.jsdelivr.net/npm/animejs@3.2.0/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/@next-theme/pjax@0.4.0/pjax.min.js"></script>
<script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>
  <script>
var pjax = new Pjax({
  selectors: [
    'head title',
    '.page-configurations',
    '.main-inner',
    '.post-toc-wrap',
    '.languages',
    '.pjax'
  ],
  analytics: false,
  cacheBust: false,
  scrollRestoration: false,
  scrollTo: !CONFIG.bookmark.enable
});

document.addEventListener('pjax:success', () => {
  pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
  NexT.boot.refresh();
  // Define Motion Sequence & Bootstrap Motion.
  if (CONFIG.motion.enable) {
    NexT.motion.integrator
      .init()
      .add(NexT.motion.middleWares.subMenu)
      .add(NexT.motion.middleWares.postList)
      .bootstrap();
  }
  const hasTOC = document.querySelector('.post-toc');
  document.querySelector('.sidebar-inner').classList.toggle('sidebar-nav-active', hasTOC);
  document.querySelector(hasTOC ? '.sidebar-nav-toc' : '.sidebar-nav-overview').click();
  NexT.utils.updateSidebarPosition();
});
</script>


  
  <script data-pjax>
    (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
    })();
  </script>




  <script src="/js/local-search.js"></script>












  






<script data-pjax>
  (function() {
    function leancloudSelector(url) {
      return document.getElementById(url).querySelector('.leancloud-visitors-count');
    }

    function addCount(Counter) {
      const visitors = document.querySelector('.leancloud_visitors');
      const url = decodeURI(visitors.id);
      const title = visitors.dataset.flagTitle;

      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url })))
        .then(response => response.json())
        .then(({ results }) => {
          if (results.length > 0) {
            const counter = results[0];
            leancloudSelector(url).innerText = counter.time + 1;
            Counter('put', '/classes/Counter/' + counter.objectId, { time: { '__op': 'Increment', 'amount': 1 } })
              .catch(error => {
                console.error('Failed to save visitor count', error);
              });
          } else {
              Counter('post', '/classes/Counter', { title, url, time: 1 })
                .then(response => response.json())
                .then(() => {
                  leancloudSelector(url).innerText = 1;
                })
                .catch(error => {
                  console.error('Failed to create', error);
                });
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    function showTime(Counter) {
      const visitors = document.querySelectorAll('.leancloud_visitors');
      const entries = [...visitors].map(element => {
        return decodeURI(element.id);
      });
      Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({ url: { '$in': entries } })))
        .then(response => response.json())
        .then(({ results }) => {
          for (let url of entries) {
            const target = results.find(item => item.url === url);
            leancloudSelector(url).innerText = target ? target.time : 0;
          }
        })
        .catch(error => {
          console.error('LeanCloud Counter Error', error);
        });
    }

    const { app_id, app_key, server_url } = {"enable":true,"app_id":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","app_key":"lwlhdaYvNPPDLhBEGeUegbH6","server_url":null,"security":false};
    function fetchData(api_server) {
      const Counter = (method, url, data) => {
        return fetch(`${api_server}/1.1${url}`, {
          method,
          headers: {
            'X-LC-Id'     : app_id,
            'X-LC-Key'    : app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };
      if (CONFIG.page.isPost) {
        if (location.hostname == '127.0.0.1' || location.hostname == 'localhost') ;
        else addCount(Counter);
      }
      if (document.querySelectorAll('.post-title-link').length >= 1 || document.querySelectorAll('.post-title').length >= 1) {
        showTime(Counter);
      }
    }

    const api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${app_id.slice(0, 8).toLowerCase()}.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(response => response.json())
        .then(({ api_server }) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>


    <div class="pjax">
  

  
      <script>
  if (typeof MathJax === 'undefined') {
    window.MathJax = {
      tex: {
        inlineMath: {'[+]': [['$', '$']]},
        tags: 'ams'
      },
      options: {
        renderActions: {
          findScript: [10, doc => {
            document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
              const display = !!node.type.match(/; *mode=display/);
              const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
              const text = document.createTextNode('');
              node.parentNode.replaceChild(text, node);
              math.start = {node: text, delim: '', n: 0};
              math.end = {node: text, delim: '', n: 0};
              doc.math.push(math);
            });
          }, '', false],
          insertedScript: [200, () => {
            document.querySelectorAll('mjx-container').forEach(node => {
              const target = node.parentNode;
              if (target.nodeName.toLowerCase() === 'li') {
                target.parentNode.classList.add('has-jax');
              }
            });
          }, '', false]
        }
      }
    };
    const script = document.createElement('script');
    script.src = '//cdn.jsdelivr.net/npm/mathjax@3.1.0/es5/tex-mml-chtml.js';
    script.defer = true;
    document.head.appendChild(script);
  } else {
    MathJax.startup.document.state(0);
    MathJax.typesetClear();
    MathJax.texReset();
    MathJax.typeset();
  }
</script>

    

  
<script>
NexT.utils.loadComments('#valine-comments', () => {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js', () => {
    new Valine(Object.assign({
      el  : '#valine-comments',
      path: "2020/【ZROI-2020-十连测】Day1/",
    }, {"enable":true,"appId":"Tw3wqSuCQwL4zK5pGCd6BkKa-gzGzoHsz","appKey":"lwlhdaYvNPPDLhBEGeUegbH6","placeholder":"Just go go","avatar":"mm","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-cn","visitor":false,"comment_count":true,"recordIP":true,"serverURLs":null,"enableQQ":true,"requiredFields":[]}
    ));
  }, window.Valine);
});
</script>

    </div>
</body>
</html>
